package java0412;

import java.util.Stack;

public class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}

class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
}

class Solution {

    // 删除链表的倒数第N个节点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        ListNode cur1 = head;
        for (int i = 1; i < n; i++) {
            if (cur1 != null) {
                cur1 = cur1.next;
            }else {
                return null;
            }
        }
        ListNode pre = null;
        ListNode delete = head;
        for (; cur1.next != null; cur1 = cur1.next) {
            pre = delete;
            delete = delete.next;
        }
        if (pre == null) {
            return head.next;
        }
        pre.next = delete.next;
        return head;
    }

    // 反转链表
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = head.next;
        while (next != null) {
            cur.next = pre;
            pre = cur;
            cur = next;
            next = next.next;
        }
        cur.next = pre;
        return cur;
    }

    // 移除链表元素
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        ListNode pre = head;
        ListNode cur = head.next;
        for (; cur != null; cur = cur.next) {
            if (cur.val == val) {
                pre.next = cur.next;
                continue;
            }
            pre = cur;
        }
        if (head.val == val) {
            head = head.next;
        }
        return head;
    }

    // 奇偶链表
    // 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
    //
    //请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        ListNode oddNode = new ListNode(0);
        ListNode oddCur = oddNode;
        ListNode evenNode = new ListNode(0);
        ListNode evenCur = evenNode;
        ListNode cur = head;
        ListNode next = cur.next;
        int num = 1;
        while (next != null) {
            if (num % 2 != 0) {
                oddCur.next = cur;
                oddCur = oddCur.next;
            }else {
                evenCur.next = cur;
                evenCur = evenCur.next;
            }
            num++;
            cur.next = null;
            cur = next;
            next = next.next;
        }
        if (num % 2 != 0) {
            oddCur.next = cur;
            oddCur = oddCur.next;
        }else {
            evenCur.next = cur;
        }
        oddCur.next = evenNode.next;
        return oddNode.next;
    }
    private int length(ListNode head) {
        ListNode cur = head;
        int length = 0;
        for (; cur != null; cur = cur.next) {
            length++;
        }
        return length;
    }

    // 两数相加
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) {
            return null;
        }
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode ret = new ListNode(0);
        int length1 = length(l1);
        int length2 = length(l2);
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        ListNode pre1 = null;
        ListNode pre2 = null;
        ListNode cur = ret;
        int carry = 0;
        while (cur1 != null && cur2 != null) {
            pre1 = cur1;
            pre2 = cur2;
            int sum = pre1.val + pre2.val + carry;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            carry = sum / 10;
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        if (length1 > length2) {
            while (cur1 != null) {
                pre1 = cur1;
                int sum = pre1.val + carry;
                cur.next = new ListNode(sum % 10);
                carry = sum / 10;
                cur1 = cur1.next;
                cur = cur.next;
            }
        }else if (length1 < length2){
            while (cur2 != null) {
                pre2 = cur2;
                int sum = pre2.val + carry;
                cur.next = new ListNode(sum % 10);
                carry = sum / 10;
                cur2 = cur2.next;
                cur = cur.next;
            }
        }
        if (carry != 0) {
            cur.next = new ListNode(carry);
        }
        return ret.next;
    }

    // 扁平化多级双向链表
//    public Node flatten(Node head) {
//        Stack<Node> stack = new Stack<>();
//        if (head == null) {
//            return null;
//        }
//        Node ret = new Node();
//        Node cur = ret;
//        while (cur != null) {
//            if (cur.next == null) {
//                if ()
//            }
//        }
//    }
}
